package leetcode.code0866;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	int max = (int) 1e4;
	static int len;
	static Integer[] pps;
	static {
		List<Integer> list = new ArrayList<>();
		for (int i = 2; i < 10; i++) {
			if (isPrime(i)) {
				list.add(i);
			}
		}
		pps(list, 0, 10);
		list.add(100030001);// 我从未见过如此厚颜无耻之徒
		pps = list.toArray(new Integer[0]);
		Arrays.sort(pps);
		len = pps.length;
	}

	public int primePalindrome(int n) {
		int l = 0, r = len - 1;
		int ans = 0, cur = 0;
		while (l <= r) {
			int m = l + ((r - l) >> 1);
			if ((cur = pps[m]) == n) {
				return pps[m];
			} else if (cur > n) {
				ans = cur;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

	private static void pps(List<Integer> list, int base, int mul) {
		if (mul >= 100000) {
			return;
		}
		int start = base == 0 ? 1 : 0;
		for (int i = start; i < 10; i++) {
			int cur = base * 10 + i;
			int mirror = mirror(cur);
			int num1 = cur * mul + mirror;
			if (isPrime(num1)) {
				list.add(num1);
			}
			if (mul <= 1000) {
				for (int j = 0; j < 10; j++) {
					num1 = cur * mul * 10 + j * mul + mirror;
					if (isPrime(num1)) {
						list.add(num1);
					}
				}
			}
			pps(list, cur, mul * 10);
		}
	}

	private static int mirror(int cur) {
		int ans = 0;
		while (cur > 0) {
			int low = cur % 10;
			cur /= 10;
			ans = ans * 10 + low;
		}
		return ans;
	}

	public static boolean isPrime(int num) {
		if ((num & 1) == 0) {
			if (num == 2) {
				return true;
			}
			return false;
		}
		for (int i = 2; i <= Math.sqrt(num); i++) {
			if (num % i == 0) {
				return false;
			}
		}
		return true;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(7, this.primePalindrome(6));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(11, this.primePalindrome(8));

	}

	@Override
	public void debug3() {
		HelpDebug.compare(101, this.primePalindrome(13));

	}

	@Override
	public void debug4() {
		HelpDebug.compare(100030001, this.primePalindrome(9989900));

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
